package stackqueuemap;

public class Test {
    public static void main(String[] args) {
        findKth(new int[]{1,3,5,2,2},5,3);
    }
    static int res = 0;
    public static int findKth (int[] a, int n, int K) {
        // write code here
        // 快排思想
        quickSort(a, 0, n-1, K);
        return res;
    }
    private static void quickSort(int[] arr, int left, int right, int k) {
        if  (left >= right) {
            return;
        }
        // 找基准值（基准所在位置即为最终位置）
        int pivotIndex = partition(arr, left, right);
        System.out.println("index = " + pivotIndex);
        if (pivotIndex == k-1) {
            res = arr[pivotIndex];
            return;
        }
        quickSort(arr, left, pivotIndex-1, k);
        quickSort(arr, pivotIndex+1, right, k);
    }

    // hoare
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int index = left;
        while (left < right) {
            while (left < right && arr[right] <= pivot) {
                right --;
            }
            while (left < right && arr[left] >= pivot) {
                left ++;
            }
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
        }
        int tmp = arr[left];
        arr[left] = arr[index];
        arr[index] = tmp;
        return left;
    }
}
